package medium任务调度器;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<Character, Integer>();
        // 最多的执行次数
        int maxExec = 0;
        for (char ch : tasks) {
            int exec = freq.getOrDefault(ch, 0) + 1;
            freq.put(ch, exec);
            maxExec = Math.max(maxExec, exec);
        }

        // 具有最多执行次数的任务数量
        int maxCount = 0;
        Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();
        for (Map.Entry<Character, Integer> entry : entrySet) {
            int value = entry.getValue();
            if (value == maxExec) {
                ++maxCount;
            }
        }

        return Math.max((maxExec - 1) * (n + 1) + maxCount, tasks.length);
    }
}


/*
    我们首先考虑所有任务种类中执行次数最多的那一种，记它为 \texttt{A}A，的执行次数为 \textit{maxExec}maxExec。

我们使用一个宽为 n+1n+1 的矩阵可视化地展现执行 \texttt{A}A 的时间点。其中任务以行优先的顺序执行，没有任务的格子对应 CPU 的待命状态。由于冷却时间为 nn，因此我们将所有的 \texttt{A}A 排布在矩阵的第一列，可以保证满足题目要求，并且容易看出这是可以使得总时间最小的排布方法，对应的总时间为：

(\textit{maxExec} - 1)(n + 1) + 1
(maxExec−1)(n+1)+1

同理，如果还有其它也需要执行 \textit{maxExec}maxExec 次的任务，我们也需要将它们依次排布成列。例如，当还有任务 \texttt{B}B 和 \texttt{C}C 时，我们需要将它们排布在矩阵的第二、三列。



如果需要执行 \textit{maxExec}maxExec 次的任务的数量为 \textit{maxCount}maxCount，那么类似地可以得到对应的总时间为：

(\textit{maxExec} - 1)(n + 1) + \textit{maxCount}
(maxExec−1)(n+1)+maxCount

读者可能会对这个总时间产生疑问：如果 \textit{maxCount} > n+1maxCount>n+1，那么多出的任务会无法排布进矩阵的某一列中，上面计算总时间的方法就不对了。我们把这个疑问放在这里，先「假设」一定有 \textit{maxCount} \leq n+1maxCount≤n+1。

处理完执行次数为 \textit{maxExec}maxExec 次的任务，剩余任务的执行次数一定都小于 \textit{maxExec}maxExec，那么我们应当如何将它们放入矩阵中呢？一种构造的方法是，我们从倒数第二行开始，按照反向列优先的顺序（即先放入靠左侧的列，同一列中先放入下方的行），依次放入每一种任务，并且同一种任务需要连续地填入。例如还有任务 \texttt{D}D，\texttt{E}E 和 \texttt{F}F 时，我们会按照下图的方式依次放入这些任务。



对于任意一种任务而言，一定不会被放入同一行两次（否则说明该任务的执行次数大于等于 \textit{maxExec}maxExec），并且由于我们是按照列优先的顺序放入这些任务，因此任意两个相邻的任务之间要么间隔 nn（例如上图中位于同一列的相同任务），要么间隔 n+1n+1（例如上图中第一列和第二列的 \texttt{F}F），都是满足题目要求的。因此如果我们按照这样的方法填入所有的任务，那么就可以保证总时间不变，仍然为：

(\textit{maxExec} - 1)(n + 1) + \textit{maxCount}
(maxExec−1)(n+1)+maxCount

当然，这些都建立在我们的「假设」之上，即我们不会填「超出」n+1n+1 列。但读者可以想一想，如果我们真的填「超出」了 n+1n+1 列，会发生什么呢？



上图给出了一个例子，此时 n+1=5n+1=5 但我们填了 77 列。标记为 \texttt{X}X 的格子表示 CPU 的待命状态。看上去我们需要 (5-1) \times 7 + 4 = 32(5−1)×7+4=32 的时间来执行所有任务，但实际上如果我们填「超出」了 n+1n+1 列，那么所有的 CPU 待命状态都是可以省去的。这是因为 CPU 待命状态本身只是为了规定任意两个相邻任务的执行间隔至少为 nn，但如果列数超过了 n+1n+1，那么就算没有这些待命状态，任意两个相邻任务的执行间隔肯定也会至少为 nn。此时，总执行时间就是任务的总数 |\textit{task}|∣task∣。

同时我们可以发现：

如果我们没有填「超出」了 n+1n+1 列，那么图中存在 00 个或多个位置没有放入任务，由于位置数量为 (\textit{maxExec} - 1)(n + 1) + \textit{maxCount}(maxExec−1)(n+1)+maxCount，因此有：

|\textit{task}| < (\textit{maxExec} - 1)(n + 1) + \textit{maxCount}
∣task∣<(maxExec−1)(n+1)+maxCount

如果我们填「超出」了 n+1n+1 列，那么同理有：

|\textit{task}| > (\textit{maxExec} - 1)(n + 1) + \textit{maxCount}
∣task∣>(maxExec−1)(n+1)+maxCount

因此，在任意的情况下，需要的最少时间就是 (\textit{maxExec} - 1)(n + 1) + \textit{maxCount}(maxExec−1)(n+1)+maxCount 和 |\textit{task}|∣task∣ 中的较大值。
 */
